package primary.code08;

import lombok.extern.slf4j.Slf4j;
import primary.util.ArrayUtils;

import java.util.*;

/**
 * 问题：岛屿数量
 * <p>
 * 一个矩阵中只有0（水）和1（陆地）两种值，每个陆地只能与上、下、左、右方向上的陆地相联
 * 如果有一片陆地相联，则这一片陆地被称为一座岛屿。
 * 请问：给定的矩阵中，有多少个岛屿？
 * <p>
 * 分析一
 * <p>
 * 将矩阵看作是无向图，“元素1” 与上、下、左、右方向的“元素1” 有边
 * 遍历矩阵的每个元素，但遇到1时，启动一次洪水覆盖并且岛屿数量+1
 * 洪水覆盖：本质是一次BFS/DFS，遍历过程中将元素修改为0
 */
@Slf4j
public class Code02_NumIslands_1 {

    public static int numIslands(int[][] arr) {
        int num = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] == 1) {
                    floodFill(arr, i, j);
                    num++;
                }
            }
        }
        return num;
    }

    private static void floodFill(int[][] arr, int i, int j) {
        log.info("flood fill, i: {}, j: {}", i, j);
        Queue<Location> queue = new LinkedList<>();
        Set<Location> visited = new HashSet<>();
        Location loc = new Location(i, j);
        queue.add(loc);
        visited.add(loc);
        while (!queue.isEmpty()) {
            Location poll = queue.poll();
            arr[poll.x][poll.y] = 0;
            log.info("put zero, x: {}, y: {}", poll.x, poll.y);
            Location left = new Location(poll.x - 1, poll.y);
            Location right = new Location(poll.x + 1, poll.y);
            Location up = new Location(poll.x, poll.y - 1);
            Location down = new Location(poll.x, poll.y + 1);
            Location[] neighbors = {left, right, up, down};
            for (Location neighbor : neighbors) {
                if (neighbor.isValidate(arr.length, arr[0].length) && arr[neighbor.x][neighbor.y] == 1 && !visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    static class Location {
        public int x;
        public int y;

        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public boolean isValidate(int width, int height) {
            if (x < 0 || x >= width || y < 0 || y >= height) {
                return false;
            }
            return true;
        }
    }

    public static void main(String[] args) {
        int[][] arr = {
                {0, 1, 1, 0, 0},
                {0, 1, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 1},
                {1, 1, 0, 0, 1}
        };
        ArrayUtils.print(arr);
        int num = numIslands(arr);
        log.info("{}", num);
    }
}
